\subsection{Decentralized intervention decisions}
\label{sec:decentralized}
In this section, we analyze diffusion processes using the
non-cooperative game model defined in Section
\ref{sec:intervention-framework}. More specifically, we consider the
games with static connections, which means we assume there are no
behavioral changes. Therefore, by Equation \ref{eqn:cost}, the cost
function for $v$ can be simplified as
\[\cost_v\left(\bar{a},d\right) = C_v a_v +(1-a_v)L_v\cdot p_v\left(\bar{a},d\right)\]
As defined in Section \ref{sec:intervention-framework},
$p_v\rb{\bar{a},d}$ denotes the probability that $v$ gets infected, if
the disease starts at a random initial node in the $d$-neighborhood of
$v$.

Under the non-cooperative game model, we are interested in answering the following questions:
\begin{enumerate}
\item Under what conditions do NE exist, when information (about the
  individual strategies and disease states) is available only within
  the $d$-neighborhood?  If NE exist, when are they unique and how
  robust are they to perturbations in the network or locality of
  information?  What is the computational complexity of finding NE or
  reaching NE via best-response dynamics?  What is the effect of the
  underlying network (e.g., the degree sequence and conductance)?  Can
  we characterize the kinds of nodes that tend to get vaccinated in
  any NE?
\item Price of anarchy: Find a vaccination strategy $\vec{a}$ that
  minimizes the total cost.  What is the maximum ratio of the cost of
  a social optimum and cost of NE (referred to as the price of
  anarchy)?  What are practical strategies that cause convergence to a
  socially desirable NE?
\end{enumerate}

\subsubsection{Our results}
The results in this section are published in
\cite{kumar+rss:icdcs}. There we have considered the special case
where $p(e)=1$ for all $e$ and intervention are perfect. We find that
the parameter $d$ has a significant role in the structure of the
resulting games.
\begin{enumerate}
\item For $d=1$, a pure NE always exists and can be found by best
  response dynamics; that is, every sequence of best response steps by
  the individual players converges to a pure NE. Finding the NE with
  least cost is NP-complete. The price of anarchy is $\Delta+1$,
  where $\Delta$ is the maximum degree in the contact graph.
\item For $d=\infty$, a pure NE always exists and can be found by best
  response dynamics. The price of anarchy is $O(1/\alpha(G))$, where
  $\alpha(G)$ is the vertex expansion of graph $G$.
\item For $d\in \rb{1,\infty}$, there always exist instances which
  have no pure NE. Further, deciding if a pure NE exists is
  NP-complete.
\end{enumerate}

\subsubsection{Open problems}
I may try to think about the following open problems if time allows.
\begin{enumerate}
\item Solve the general model with arbitrary disease transmission
  probability. This problem is much more challenging to handle. One of
  the difficulties we face in terms of best response function is that
  with probabilistic transmission, even the calculation of the cost
  for an individual node can be shown to be \#P-hard
  \cite{valiant79}. Efficient approximations (using Monte Carlo
  simulations) can be computed, however, leading to the question: do
  ``approximate'' NE exist and can they be efficiently found?
\item Explore more on the structures of NE and its implications on
  public policy. In the simulation using the preferential attachment
  graph model \cite{kumar+rss:icdcs}, we have observed that high
  degree nodes tend to get vaccinated in NE (when they exist). It
  would be nice to have some theoretical proofs about such
  observations.
\item Analyze Stackelberg strategies, in which the choices of some
  nodes can be control by the policy planer, and the goal would be to
  design low cost strategies that cause the remaining nodes to reach a
  ``good'' NE.
\end{enumerate}
